import java.util.LinkedList;
import java.util.Queue;

public class Solve {
    private static final int[] dx = {-1,0,0,1};
    private static final int[] dy = {0,-1,1,0};
    private boolean[][] vis;
    public void solve(char[][] board) {
        // 被围绕的区域
        // https://leetcode.cn/problems/surrounded-regions/
        int n = board.length;
        int m = board[0].length;
        vis = new boolean[n][m];
        for (int j = 0; j < m; j++) {
            if (board[0][j] == 'O') {
                bfs(board, 0, j);
            }
            if (board[n-1][j] == 'O') {
                bfs(board, n-1, j);
            }
        }
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][m-1] == 'O') {
                bfs(board, i, m-1);
            }
        }
        for (int i = 1; i < n-1; i++) {
            for (int j = 1; j < m-1; j++) {
                if (board[i][j] == 'O' && !vis[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void bfs(char[][] board, int row, int col) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{row, col});
        vis[row][col] = true;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int i = tmp[0];
            int j = tmp[1];
            for (int k = 0; k < 4; k++) {
                int newRow = i + dx[k];
                int newCol = j + dy[k];
                if (newRow >= 0 && newRow < board.length
                        && newCol >= 0 && newCol < board[0].length
                        && !vis[newRow][newCol] && board[newRow][newCol] == 'O') {
                    queue.offer(new int[]{newRow, newCol});
                    bfs(board, newRow, newCol);
                }
            }
        }
    }
}
